package main

import (
	"fmt"
	"time"
)

//快速排序

//方法一：key=num[(start+end)/2] 较慢
func quick1(num []int, start, end int) {
	if start < end {
		i, j, key := start, end, num[(start+end)/2]
		for i <= j && num[i] < key {
			i++
		}
		for i <= j && key < num[j] {
			j--
		}
		if i <= j {
			num[i], num[j] = num[j], num[i]
			i++
			j--
		}
		if i < end {
			quick1(num, i, end)
		}
		if start < j {
			quick1(num, start, j)
		}
	}
}

//方法二 key = num[0] 速度较快
func quick2(num []int) {
	if len(num) <= 1 {
		return
	}
	key := num[0] //以第一个元素作为key
	l, r := 0, len(num)-1
	for i := 1; i <= r; {
		if num[i] > key {
			num[i], num[r] = num[r], num[i]
			r--
		} else {
			num[i], num[l] = num[l], num[i]
			l++
			i++
		}
	}
	quick2(num[:l])
	quick2(num[l+1:])
}

func main() {
	//方法一：
	arr1 := []int{3, 7, 9, 8, 38, 93, 12, 222, 45, 93, 23, 84, 65, 2}
	time1 := time.Now()
	quick1(arr1, 0, len(arr1)-1)
	end1 := time.Since(time1)
	fmt.Println("方法一：", arr1, end1)

	arr2 := []int{3, 7, 9, 8, 38, 93, 12, 222, 45, 93, 23, 84, 65, 2}
	time2 := time.Now()
	quick2(arr2)
	end2 := time.Since(time2)
	fmt.Println("方法二：", arr2, end2)

}
